package com.brett.frame.learn.sort;

import com.brett.frame.learn.sort.base.Sort;
import com.brett.frame.learn.util.DataBuilder;
import com.brett.frame.learn.util.Tools;

/**
 * 基数排序，对桶排序的扩展
 * @author lenovo
 *
 */
public class RadixSort implements Sort {
	DataBuilder builder = new DataBuilder();

	/**
	 * 需1倍的存储空间
	 */
	@Override
	public int[] sort(int[] arr) {
		int maxBit = maxBit(arr);
		int exp = 1;
		int[] bucket = new int[10]; // 存储位数据的桶
		int[] temp=new int[arr.length];// 临时存放中间态数据
		for (int i = 0; i < maxBit; i++) {
			Tools.initZero(bucket);
			for (int j = 0; j < arr.length; j++) {
				int bit = arr[j] / exp % 10; // 取指定位的值
				bucket[bit]++;
			}
			builder.printArr("bucket1",bucket);
			 for(int j=1;j<10;j++) {
				 bucket[j]+=bucket[j-1];
			 }
			 builder.printArr("bucket2",bucket);
 
		 for(int j=arr.length-1;j>=0;j--) {  // 一定要从后往前循环
				int bit = arr[j] / exp % 10; // 取指定位的值
				temp[bucket[bit]-1]=arr[j];
				bucket[bit]--;
		 }
		 for(int j=0;j<arr.length;j++) {
			 arr[j]=temp[j];
		 }
			builder.printArr("maxBit"+(1+i), arr);
			exp *= 10;
		}
		return arr;
	}

	/**
	 * 需要10倍的空间
	 * @param arr
	 * @return
	 */
	public int[] sortX10(int[] arr) {
		int maxBit = maxBit(arr);
		int exp = 1;
		int[] bucket = new int[10]; // 存储位数据的桶
		int[][] data = new int[10][arr.length]; // 存储位相同时的数据

		for (int i = 0; i < maxBit; i++) {
			Tools.initZero(bucket);
			Tools.initZero(data);
			for (int j = 0; j < arr.length; j++) {
				int bit = arr[j] / exp % 10; // 取指定位的值
				bucket[bit]++;
				data[bit][bucket[bit] - 1] = arr[j];
			}

			builder.printArr("maxBit" + (i + 1), data);
			int index = 0;
			for (int j = 0; j < 10; j++) {
				if (bucket[j] > 0) {
					for (int b = 0; b < bucket[j]; b++) {
						arr[index++] = data[j][b];
					}
				}
			}
			builder.printArr("maxBit", arr);
			exp *= 10;
		}
		return arr;
	}

	public int maxBit(int[] arr) {
		int max = 0;
		for (int i = 0; i < arr.length; i++) {
			int count = 1;
			int tmp = arr[i];
			while (tmp / 10 != 0) {
				tmp /= 10;
				count++;
			}
			if (count > max) {
				max = count;
			}
		}
		return max;
	}
}
